package leetcode_1401_1500;

import java.util.Arrays;

public class LeeCode_1463 {
    public static void main(String[] args) {
        System.out.println(cherryPickup(new int[][]{{3, 1, 1}, {2, 5, 1}, {1, 5, 5}, {2, 1, 1}}));
    }
    private static int cherryPickup(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] g = new int[n][n];
        int[][] f = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(g[i], -1);
            Arrays.fill(f[i], -1);
        }
        f[0][n - 1] = grid[0][0] + grid[0][n - 1];
        for (int i = 1; i < m; i++) {
            for (int j1 = 0; j1 < n; j1++) {
                for (int j2 = 0; j2 < n; j2++) {
                    int best = -1;
                    for (int dj1 = j1 - 1; dj1 <= j1 + 1; dj1++){
                        for(int dj2 = j2 - 1; dj2 <= j2 + 1; dj2++){
                            if (dj1 >= 0 && dj1 < n && dj2 >= 0 && dj2 < n && f[dj1][dj2] != -1){
                                best = Math.max(best, f[dj1][dj2] + (j1 == j2 ? grid[i][j1] : grid[i][j1] + grid[i][j2]));
                            }
                        }
                    }
                    g[j1][j2] = best;
                }
            }
            int[][] tmp = f;
            f = g;
            g = tmp;
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                ans = Math.max(ans, f[i][j]);
            }
        }
        return ans;
    }
}